package nl.rug.ai.believer.model;

import java.util.ArrayList;

/**
 * This class is responsible for doing any actual evaluations. For this purpose, the core will provide it
 * with a copy of current state.
 * @author S1849700
 *
 */
public class Evaluator {
	
	private State state;

	Evaluator(State state) {
		this.state = state;
	}
	
	/**
	 * external interface for the rest of the package. This method splits the formula on the turnstyle and then calls 
	 * eval() to do the rest. (calls it on all worlds if there is no world before the turnstyle.
	 * @param formula  the formula to evaluate.
	 * @return the result of the evaluation.
	 */
	boolean evaluate(String formula) {
		int turnstylePos = formula.indexOf(Util.turnstyle);
		if (turnstylePos != -1) {
			if (formula.substring(0, turnstylePos).trim().equals("")) {
				// if there is nothing before the turnstyle, by convention, we want to evaluate on all worlds.
				String myFormula = formula.substring(turnstylePos + Util.turnstyle.length()).trim();
				for (World world : state.getWorlds()) { 
					if(!eval(myFormula, world)) { // must be true on all worlds.
						return false;
					}
				} 
				// if it didn't return before this point, it indeed is true.
				// incidentally, this causes all formula's to be true which are made when there are no worlds at all...
				return true;
			}
			else {
				World world = state.getWorld(formula.substring(0, turnstylePos).trim());
				if (world == null) { // can't eval, origin world does not exist
					throw new RuntimeException("Cannot evaluate, world before the turnstyle does not exist.");
				}
				return eval(formula.substring(turnstylePos + Util.turnstyle.length()).trim(), world);
			}
		}
		throw new RuntimeException("Cannot evaluate, a formula without turnstyle is not a valid formula.");
	}
	
	
	/**
	 * this method calls itself recursively (if needed) to solve  the formula. 
	 * @param formula the formula to solve
	 * @param world  the world in which to solve it.
	 * @return the result of the evaluation
	 */
	private boolean eval(String formula, World world) {
		if (formula.trim().isEmpty()) {
			Util.debug("Empty formula.");
			return false;
		}
		String myFormula = removeOuterParenthesis(formula);
		while (!myFormula.equals(removeOuterParenthesis(myFormula))) {
			myFormula = removeOuterParenthesis(myFormula);  // remove arbitrary amount of parenthesis.
		}
		String formulaParts[];
		formulaParts = splitOperator(Util.equals, myFormula);
		if (formulaParts != null) { // true if both sides are equal
			Util.debug("Chose the equals operator in: " + myFormula);
			return eval(formulaParts[0], world) == eval(formulaParts[1], world);
		}
		formulaParts = splitOperator(Util.implies, myFormula);
		if (formulaParts != null) { // true if first part does not hold, or if first and second do.
			Util.debug("Chose the implies operator in: " + myFormula);
			if (eval(formulaParts[0], world)) {
				return eval(formulaParts[1], world);
			}
			else {
				return true;
			}
		}
		formulaParts = splitOperator(Util.or, myFormula);
		if (formulaParts != null) { // true if either side of the OR is true.
			Util.debug("Chose the or operator in: " + myFormula);
			return eval(formulaParts[0], world) || eval(formulaParts[1], world);
		}
		formulaParts = splitOperator(Util.and, myFormula);
		if (formulaParts != null) { // true only if both sides are true
			Util.debug("Chose the and operator in: " + myFormula);
			return eval(formulaParts[0], world) && eval(formulaParts[1], world);
		}
		
		String unary = obtainUnaryOperator(Util.not, myFormula);
		if (unary != null) { // NOT operator just reverses the outcome.
			Util.debug("Chose the not operator in: " + myFormula);
			return !eval(unary, world);
		}
		
		unary = obtainUnaryOperator(Util.belief, myFormula);
		if (unary != null) { 
			Util.debug("Chose the belief operator in: " + myFormula);
			Agent agent = extractAgent(myFormula);
			if (agent == null) {
				Util.debug("Invalid agent in: " + myFormula);
				throw new RuntimeException("Invalid agent"); // invalid agent, can't evaluate.
			}
			formulaParts = splitComplexUnaryOperator(Util.conditional, unary);
			if (formulaParts == null) { // regular belief
				for(World myWorld : state.getBeliefs(agent, world)) {
					if (!eval(unary, myWorld)) {
						return false;
					}
				}
				return true;
			}
			// conditional belief
			ArrayList<ArrayList<World>> orderedBeliefs = state.getOrderedBeliefs(agent, world);
			if (orderedBeliefs == null || orderedBeliefs.size() == 0) {
				throw new RuntimeException("Program entered illegal state, can't continue evaluations.");
			}
			boolean found = false;
			for (ArrayList<World> set : orderedBeliefs) {
				for (World myWorld : set) {
					// found a world where the condition holds
					if (eval(formulaParts[0], myWorld)) {
						// if the rest of the formula does not hold on *any* world where the condition does, the
						// total result is false.
						if(!eval(formulaParts[1], myWorld)) {
							return false; 
						}
						found = true;
					}
				}
				// means one of the ordered groups of worlds contained one or more worlds where this was true.
				// we do not want to search lower-believed worlds in that case.
				if (found) {
					break;
				}
			}
			if (!found) {
				Util.debug("No world match conditional, defaulting to false.");
				return false;
			}
			// If we are here, then one or more worlds were found where the conditional holds, and the rest as well. 
			return true;
		}
		unary = obtainUnaryOperator(Util.knowledge, myFormula);
		if (unary != null) { 
			Util.debug("Chose the knowledge operator in: " + myFormula);
			Agent agent = extractAgent(myFormula);
			if (agent == null) {
				Util.debug("Invalid agent in: " + myFormula);
				throw new RuntimeException("Invalid agent"); // invalid agent, can't evaluate.
			}
			// get all worlds known to this agent, if even 1 of them is false, it is not knowledge, otherwise true.
			for(World myWorld : state.getKnowledgeWorlds(agent, world)) {
				if (!eval(unary, myWorld)) {
					return false;
				}
			}
			return true;
		}
		formulaParts = splitComplexUnaryOperator(Util.update, myFormula);
		if (formulaParts != null) { 
			Util.debug("Chose the update operator in: " + myFormula);
			
			// search for agents
			ArrayList<Agent> agents = extractAgents(myFormula.substring(Util.update.length()));
			// make a copy of the state, and use a new clone of it, as we will temporarily want to change some things.
			State old = state; 
			state = state.clone();
			
			// collect worlds which are true according to our update condition.
			ArrayList<World> targetWorlds = new ArrayList<World>();
			for (World target : state.getWorlds()) {
				if (eval(formulaParts[0], target)) {
					targetWorlds.add(target);
				}
			}
			
			World myWorld = world;
			// if no agents were found, this command was meant for all. (special case)
			if (agents == null) {
				state.performUpdate(targetWorlds);
			}
			else {
				myWorld = state.performUpdate(targetWorlds, agents, world);
			}

			// Evaluate if after the update, the formula holds.
			boolean result = eval(formulaParts[1], myWorld);

			state = old; // return state to normal
			return result;
		}
		formulaParts = splitComplexUnaryOperator(Util.radical_upgrade, myFormula);
		if (formulaParts != null) { 
			Util.debug("Chose the radical upgrade operator in: " + myFormula);
			
			// search for agents
			ArrayList<Agent> agents = extractAgents(myFormula.substring(Util.radical_upgrade.length()));
			// make a copy of the state, and use a new clone of it, as we will temporarily want to change some things.
			State old = state; 
			state = state.clone();
			
			// determine worlds matching the upgrade condition
			ArrayList<World> targetWorlds = new ArrayList<World>();
			for (World target : state.getWorlds()) {
				if (eval(formulaParts[0], target)) {
					targetWorlds.add(target);
				}
			}
			
			World myWorld = world;
			// if no agents were found, this command was meant for all. (special case)
			if (agents == null) {
				state.performUpgrade(targetWorlds);
			}
			else {
				myWorld = state.performRadicalUpgrade(targetWorlds, agents, world);
			}

			
			// Evaluate if after the upgrade, the formula holds.
			boolean result = eval(formulaParts[1], myWorld);
			
			state = old; // return state to normal
			return result;
		}
		formulaParts = splitComplexUnaryOperator(Util.conservative_upgrade, myFormula);
		if (formulaParts != null) { 
			Util.debug("Chose the conservative upgrade operator in: " + myFormula);
			
			// make a copy of the state, and use a new clone of it, as we will temporarily want to change some things.
			State old = state; 
			state = state.clone();
			ArrayList<World> targetWorlds = new ArrayList<World>();
			
			for (Agent agent : state.getAgents()) {
				ArrayList<ArrayList<World>> orderedBeliefs = state.getOrderedBeliefs(agent, world);
				if (orderedBeliefs == null || orderedBeliefs.size() == 0) {
					throw new RuntimeException("Program entered illegal state, can't continue evaluations.");
				}
				boolean found = false;
				for (ArrayList<World> set : orderedBeliefs) {
					for (World myWorld : set) {
						// found a world where the condition holds
						if (eval(formulaParts[0], myWorld)) {
							targetWorlds.add(myWorld);
							found = true;
						}
					}
					// means one of the ordered groups of worlds contained one or more worlds where this was true.
					// we do not want to search lower-believed worlds in that case.
					if (found) {
						break;
					}
				}
				state.performConvervativeUpgrade(targetWorlds, agent);
				targetWorlds.clear();
			}
			
			// Evaluate if after the upgrade, the formula holds.
			boolean result = eval(formulaParts[1], world);
			
			state = old; // return state to normal
			return result;
		}
		
		// if we get here, then no operators were found, thus we (should) have a single proposition left.
		if (world.containsProposition(myFormula)) {
			Util.debug("proposition " + myFormula + " was true on world: " + world.getName());
			return true;
		}
		Util.debug("proposition " + myFormula + " was false on world: " + world.getName());
		return false;
		
	}
	
	/**
	 * Obtain the agent from a formula. This should only be called on belief or knowledge operators. Missing open or close
	 * brackets will lead to an unknown agent. Since it can only contain an agent name, the start and end tags matched are
	 * the first found in the String. (note that the start tag must directly follow the B/K symbol.
	 * @param formula the formula to inspect
	 * @return the resulting agent. (or null if not found)
	 */
	private Agent extractAgent(String formula) {
		int start = formula.indexOf(Util.agentStartTag);
		int end = formula.indexOf(Util.agentEndTag);
		if (start == -1 || end == -1 || start > 1) { // more than 1 means it's not following this B or K 
			return null;
		}
		return state.getAgent(formula.substring(start + 1, end).trim());
	}
	
	/**
	 * This method returns an ArrayList containing all agents found within the agent tags. 
	 * Agents separated by the agentSeparator (as defined in the config). Throws a RuntimeException
	 * if any agents are invalid or not existent.
	 * @param formula The formula at the start of which the agent tags are expected.
	 * @return an ArrayList with the agents found, or null if no agentStartTag/end tag were found.
	 */
	private ArrayList<Agent> extractAgents(String formula) {
		int start = formula.indexOf(Util.agentStartTag);
		int end = formula.indexOf(Util.agentEndTag);
		if (start == -1 || end == -1 || start > 1) { // more than 1 means it's not following this B or K 
			return null;
		}
		ArrayList<Agent> result = new ArrayList<Agent>();
		String[] agents = formula.substring(start + 1, end).trim().split(Util.agentSeparator);
		if (agents.length == 0) {
			throw new RuntimeException("Found agent start/end tag without any agent.");
		}
		for (String agent : agents) {
			if (state.getAgent(agent.trim()) != null) {
				result.add(state.getAgent(agent.trim()));
			}
			else {
				throw new RuntimeException("Invalid/Unknown agent name: " + agent);
			}
		}
		return result;
	}
		
	/**
	 * This method removes the outer parenthesis around a string (if any) and returns the cleaned
	 * string, or the original of none were found.
	 * @param input -- the input to be cleaned
	 * @return -- the cleaned input
	 */
	private String removeOuterParenthesis(String input) {
		String myInput = input.trim();
		if (myInput.equals("")) {
			return myInput;
		}
		if (myInput.charAt(0) == '(' && myInput.charAt(myInput.length() - 1) == ')') {
			int depth = 0;
            // -1 because we want to exclude the last ) from the check, after all,that one would certainly make the depth 0.
            for(int i = 0; i < myInput.length() - 1; i++) { 
                if (myInput.charAt(i) == '(') {
                    depth++;
                }
                else if (myInput.charAt(i) == ')') {
                    depth--;
                }
                // This means the first ( gets closed somewhere (and thus there is (should be) an operator we need first.
                if (depth <= 0) {
                    return myInput;
                }
            }
            // -1 because it takes endIndex-1, thus this excludes the )
            return myInput.substring(1, myInput.length() - 1).trim();  
        }
		return myInput;
	}
	
	/**
	 * Splits the formula on the operator (if found). Returns an array containing the formula on the left in position 0
	 * and the right in position 1.  returns null if the operator was not found.
	 * @param operator  The operator to split on
	 * @param formula  the formula to search in
	 * @return an array containing the left and right side formula's of the operator. Or null if the operator was not found.
	 */
	private String[] splitOperator(String operator, String formula) {
		String myInput = formula.trim();
		int depth = 0;
		String result[] = new String[2];
        for(int i = 0; i < myInput.length(); i++) { 
    		// In this loop, we ignore all blocks that are between () 
            if (myInput.charAt(i) == '(') {
                depth++;
            }
            else if (myInput.charAt(i) == ')') {
                depth--;
            }
            // This means the first ( gets closed somewhere (and thus there is (should be) an operator we need first.
            if (depth != 0) {
                continue;
            }
            // means we found the operator we are looking for at this spot (i).
            if (myInput.startsWith(operator, i)) {
            	result[0] = myInput.substring(0, i).trim(); 
            	result[1] = myInput.substring(i + operator.length()); // start at the first char after this operator.
            	return result;
            }
        }
		// if we reach this, we didn't find our operator.
		return null;
	}
	
	/**
	 * Method returns all that follows the unary operator (not the operator itself). <agent> is considered part of the 
	 * operator. Returns null if not found.
	 * @param operator the operator to look for
	 * @param formula the formula in which to look for the operator.
	 * @return the formula following the operator or null if not found.
	 */
	private String obtainUnaryOperator(String operator, String formula) {
		String myInput = formula.trim();
		if (operator.equals(Util.not)) {
			if (myInput.startsWith(operator)) {
				return myInput.substring(operator.length());
			}
			return null;
		}
		// agentStart and End tag always follow each other (no formulas between them, just an agent name. 
		// We assume that agentStartTag follows directly after a B/K symbol.
		if (myInput.startsWith(operator + Util.agentStartTag)) { 
			if (myInput.indexOf(Util.agentEndTag) == -1) {
				throw new RuntimeException("Found an agentStartTag without matching agentEndTag");
			}
			return myInput.substring(myInput.indexOf(Util.agentEndTag) + 1); // +1 to get all that is *after* the tag.
		}
		return null;
	}
	
	/**
	 * used to split complex unary operators (update, upgrade, conditional, etc) like UPDATE(formula1)formula2.
	 * It will return formula 1 at position 0 and formula 2 and position 1 of the array. 
	 * @return
	 */
	private String[] splitComplexUnaryOperator(String operator, String formula) {
		String myInput = formula.trim();
		String result[] = new String[2];
		if (formula == null || formula.trim().equals("")) {
			return null;
		}
		if (myInput.startsWith(operator)) {
			myInput = myInput.substring(operator.length()).trim();
			ArrayList<Agent> temp = extractAgents(myInput);
			if (temp != null) {
				myInput = myInput.substring(myInput.indexOf(Util.agentEndTag) + Util.agentEndTag.length());
			}
			if (!myInput.startsWith("(")) {	
					return null;
			}
			// we start at 1, because our first char (0) is the first opening.
			int depth = 1;
	        for(int i = 1; i < myInput.length(); i++) { 
	            if (myInput.charAt(i) == '(') {
	                depth++;
	            }
	            else if (myInput.charAt(i) == ')') {
	                depth--;
	            }
	            // This means we found the closing of this block.
	            if (depth == 0) {
	            	// 1 is the position just past the opening, substring uses end-1, thus excludes the closing. (this i)
	                result[0] = myInput.substring(1, i).trim();
	                // and +1 to get all that follows the () block.
	                result[1] = myInput.substring(i + 1).trim();
	                return result;
	            }
	        }
		}
		return null; 
	}
}
